package demo1;

import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        elem = new int[10];
    }

    public void initArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void cerateHeap(){
        //创建大根堆
        for (int parent = (usedSize-1-1)/2; parent>=0; parent--) {
            //第一步：向下调整
            siftDown(parent,usedSize);
            /**
             * 起始和结束位置，节点最多为10个节点，所以以usedSize结尾，
             * 若调整中出现了某个节点比Size大说明“当前子树”调整结束了
             */

        }
    }


    private void siftDown(int parent, int usedSize) {
        int child=parent*2+1;//左子树
        while(child<usedSize){//能够进入说明一定存在子树
            //接下来进行判定，左右孩子找最大值
            if(child+1<usedSize&&elem[child]<elem[child+1]){//child+1防止数组越界
                //能进入这里说明存在右孩子
                child++;
            }
            //走出if说明找到了左右孩子中的最大值
            if(elem[child]>elem[parent]){//接下来进行交换
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                //交换完成后需要更新新的parent和child
                parent=child;
                child=parent*2+1;
            }else{
                break;//走到这里说明本身就是大根堆了，都没有需要交换的了，结束即可
            }
        }
    }


    //创建小根堆同理，只需改变调整的比较即可
    public void cerateHeap1(){
        //创建小根堆
        for (int parent = (usedSize-1-1)/2; parent>=0; parent--) {
            //第一步：向下调整
            siftDown1(parent,usedSize);
            /**
             * 起始和结束位置，节点最多为10个节点，所以以usedSize结尾，
             * 若调整中出现了某个节点比Size大说明“当前子树”调整结束了
             */

        }
    }
    private void siftDown1(int parent, int usedSize) {
        int child=parent*2+1;//左子树
        while(child<usedSize){//能够进入说明一定存在子树
            //接下来进行判定，左右孩子找最大值
            if(child+1<usedSize&&elem[child]>elem[child+1]){//child+1防止数组越界
                //能进入这里说明存在右孩子
                child++;
            }
            //走出if说明找到了左右孩子中的最大值
            if(elem[child]<elem[parent]){//接下来进行交换
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                //交换完成后需要更新新的parent和child
                parent=child;
                child=parent*2+1;
            }else{
                break;//走到这里说明本身就是大根堆了，都没有需要交换的了，结束即可
            }
        }
    }

    public void offer(int val) {
        if(isFull()){//若满了进行扩容操作
            elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=val;
        siftUp(usedSize);
        usedSize++;
    }

    private void siftUp(int child) {
        int parent=(child-1)/2;
        while(child<0||parent>=0){
            if(elem[child]>elem[parent]){
                int temp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=temp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSize==elem.length;
    }

    public void poll(){
        if(isEmpty()){//判空
            return;
        }
        //交换
        int temp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=temp;
        usedSize--;
        //向下调整
        siftDown(0,usedSize);
    }
    public boolean isEmpty() {
        return usedSize==0;
    }

    public int peek(){
        if(isEmpty()){
            return -1;
        }
        return elem[0];
    }

    /* *
     * 堆常见用法：堆排序，如从小到大排序，建大堆
     * */
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            int temp=elem[0];
            elem[0]=elem[end];
            elem[end]=temp;
            //完成交换后进行向上调整
            siftDown(0,end);
            end--;
        }
    }
}
